So hi everybody. Welcome back to AI2. We are talking about very simple decision theory.

Here the setting is we have the usual state-based agent. State-based meaning we have a world

model and by now that's a Bayesian network. We complemented that with something we don't

really understand yet which is a decision model. One of the things that we looked at

was essentially to look at utilities. We want to have a utility-based agent and we want

utilities rather than goals to drive the decisions. We also finished Bayesian networks last week

and I was basically we looked at how to construct Bayesian networks in practice and how to reason

on this, these networks. It turns out as it always does, if the topology of our world

model has good properties, which usually means something like tree-like. In AI we love trees.

Here we can even tolerate polytrees which is not that much different. If the structures

we're working with, the dependency structures we're working with are somehow tree-like,

we're expecting by now polynomial inference. It was the same thing with the constraint

networks. You can actually even do it for DPLL and even partially first order logic.

If the dependencies are well behaved, then you can do stuff polynomially. If it isn't,

then you're looking at at least exponential, maybe worse, maybe even undecidable. In this

case here everything is decidable, but that doesn't help us in practice because things

are getting so big that it could just as well be undecidable. That's really what we did.

What we didn't do is all the fun stuff where we get around the hard cases. What you can

do is inference by sampling. If you have these non-polytree, meaning cyclic, parts of your

graph, you can just cluster that automatically into derived random variables, which makes

inference go faster, but of course results worse because we're taking an approximative

worse world model. You can always compile into SAT. Anything that's decidable empirically,

you can compile into SAT and sometimes that is efficient. Then of course you can do dynamic

Bayesian networks. We're going to get into that a little bit later and then you can go

away from propositional logic into something more interesting. Some of that is actually

nicely described in the third edition of Russell Norwick. Makes good reading if you're interested

in these things. Good. We don't do that here. What we do instead is we look at decision

theory because just having clever agents is not enough. We have agents that actually act

on the world because you can't really look into this box. We're doing that because we're

synthesizing them, but when you run across an agent in the world, be it a self-driving

car or another computer science student or a fox running over the street or something

like this, there's no way to look into those. We're looking into that, but essentially unless

these agents act on the world, we have no way of understanding what they do and whether

they might be intelligent or not. That's what I'm trying to say. Good. We're going to do

decision theory and basically we're going to look at an agent, the case of an agent

in a non-deterministic world, non-deterministic in various degrees. We're going to make certain

assumptions here, but we're going to use Bayesian networks as our world model to build on. We're

going to look at utility-based agents instead of reflex agents or something like this. The

realization is that this actually gives us what we've been looking for in the last time,

namely it gives us rationality. Rationality defined as optimizing the expected outcome

over the long term. We have actions and for every action we can compute the expected utility,

whatever utility it is, we'll just assume a function into the positive reals for now.

The utility of an action given some evidence about the world, which is exactly the problem

this choice module needs to solve. Given a world model, how can I do the best action?

Where best is defined in terms of utility. That is something that's very simple in principle.

You just sum over all the states, over all the possible states that can be successor

states. You're looking at the probability of the result of your action, remember actions

don't need to be deterministic, being this state we're summing over, given that we make

an action and we have the same evidence we take as input. For each of those probabilities,

we weight that with the utility of the state we reach in there. That's the standard expected